package week_10;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class GetSkyline_218 {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<int[]> events = new ArrayList<>();

        for (int[] building : buildings) {
            int l = building[0];
            int r = building[1];
            int h = building[2];
            events.add(new int[]{l, -h});
            events.add(new int[]{r, h});
        }
        Collections.sort(events, (e1, e2) -> {
            if (e1[0] != e2[0]) return e1[0] - e2[0];
            return e1[1] - e2[1];
        });
        // 默认小根堆变大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a);
        int prev = 0;
        priorityQueue.add(prev);
        List<List<Integer>> ans = new ArrayList<>();
        for (int[] event : events) {
            int x = event[0];
            int h = event[1];
            if (h < 0) {
                priorityQueue.add(-h);
            } else {
                priorityQueue.remove(h);
            }
            int cur = priorityQueue.peek();
            if (cur != prev) {
                List<Integer> list = new ArrayList<>();
                list.add(x);
                list.add(cur);
                ans.add(list);
                prev = cur;
            }
        }
        return ans;
    }

}
